/*
 * @Author: 缄默
 * @Date: 2021-10-27 16:07:17
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-08 19:40:28
 */

//打印二叉树的边界节点

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : value(x), left(nullptr), right(nullptr) { }
    TreeNode() : value(0), left(nullptr), right(nullptr) { }
};

//用先序遍历后中序遍历建树
TreeNode *buildTree(vector<int> &preOrder, vector<int> &inOrder, int val, int left, int right);
//求树的深度
int getHight(const TreeNode* root, int hight);

void setEdgeMap(TreeNode* root, int l, vector<vector<TreeNode*>>& edgeMap);

void printLeafNotInMap(TreeNode* root, int len, vector<vector<TreeNode*>>& edgeMap);

void printMethodOne(TreeNode* root);

int main()
{
    //
    vector<int> inOrder({2, 7, 4, 8, 13, 11, 14, 1, 15, 12, 16, 9, 5, 10, 3, 6});
    vector<int> preOrder({1, 2, 4, 7, 8, 11, 13, 14, 3, 5, 9, 12, 15, 16, 10, 6});
    TreeNode *root = buildTree(preOrder, inOrder, 0, 0, (preOrder.size() - 1));
    printMethodOne(root);
    return 0;
}

TreeNode *buildTree(vector<int> &preOrder, vector<int> &inOrder, int rootIndex, int left, int right)
{
    if (left > right)
        return nullptr;
    TreeNode *root = new TreeNode(preOrder[rootIndex]);
    int index = left;
    while (index < right && preOrder[rootIndex] != inOrder[index])
    {
        index++;
    }
    //划分的是中序遍历的数组
    //第一个参数传递的是子树的根节点在先序遍历的位置
    root->left = buildTree(preOrder, inOrder, rootIndex + 1, left, index - 1);
    //根节点的右子树的位置在根节点的位置+左子树的长度+1  左子树的长度为中序遍历中根节点减去左边界
    root->right = buildTree(preOrder, inOrder, rootIndex + index - left + 1, index + 1, right);
    return root;
}


void printMethodOne(TreeNode* root) {
    if (root == nullptr) return;
    int hight = getHight(root, 0);
    vector<vector<TreeNode*>> edgeMap(hight, vector<TreeNode*>(2));
    setEdgeMap(root, 0, edgeMap);
    //打印左边界
    for (int i = 0; i != hight; i++) {
        cout << edgeMap[i][0]->value << " ";
    }
    //打印既不是左边界也不是右边界的叶子节点
    printLeafNotInMap(root, 0, edgeMap);
    //打印右边界
    for (int i = hight - 1; i != -1; i--) {
        //判断是否是最下层的一个节点
        if (edgeMap[i][0] != edgeMap[i][1]) {
            cout << edgeMap[i][1]->value << " ";
        }
    }
}

int getHight(const TreeNode* root, int hight) {
    if (root == nullptr) return hight;
    int left = getHight(root->left, hight + 1);
    int right = getHight(root->right, hight + 1);
    return left < right ? right : left;
}

//打印左侧边界
//思路：先将edgeMap【len】【0】没有赋值 第一次经过 就赋值 如果经过了就不在改动 有根据是先左子树在右子树的顺序 左子树一旦存在就经过 所以会存储下来左边界
//右边界每次都会修改为当前节点 但是同一行中最右侧边界是最后被遍历到的 所以直接赋值为当前节点即可
void setEdgeMap(TreeNode* root, int len, vector<vector<TreeNode*>>& edgeMap) {
    if (root == nullptr) return;
    edgeMap[len][0] = edgeMap[len][0] == nullptr ? root : edgeMap[len][0];
    edgeMap[len][1] = root;
    setEdgeMap(root->left, len + 1, edgeMap);
    setEdgeMap(root->right, len + 1, edgeMap);
}

//打印既不是左子树又不是右子树
//思路：先判断该节点是不是叶子节点 是不是已经存在在edgeMap中，倘若是就跳过 不是的画就输出
void printLeafNotInMap(TreeNode* root, int len, vector<vector<TreeNode*>>& edgeMap) {
    if (root == nullptr) return;
    if (root->left == nullptr && root->right == nullptr && root != edgeMap[len][0] && root != edgeMap[len][1]) {
        cout << root->value << " ";
    }
    printLeafNotInMap(root->left, len + 1, edgeMap);
    printLeafNotInMap(root->right, len + 1, edgeMap);
}


